/*
机器人在一个无限大小的网格上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令：

-2：向左转 90 度
-1：向右转 90 度
1 <= x <= 9：向前移动 x 个单位长度
在网格上有一些格子被视为障碍物。

第 i 个障碍物位于网格点  (obstacles[i][0], obstacles[i][1])

机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续该路线的其余部分。

返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。

 

示例 1：

输入: commands = [4,-1,3], obstacles = []
输出: 25
解释: 机器人将会到达 (3, 4)
示例 2：

输入: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出: 65
解释: 机器人在左转走到 (1, 8) 之前将被困在 (1, 4) 处
 

提示：

0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
答案保证小于 2 ^ 31

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/walking-robot-simulation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        
        set<pair<int, int>> ob_set;
        for(auto& i:obstacles){
            ob_set.insert(make_pair(i[0],i[1]));
        }        

        int max_dis=0;
        vector<int> direction(2,0);
        direction[0]=0;
        direction[1]=1;
        vector<vector<int>> rotate(2,vector<int>(4,0));
        rotate[0]=vector<int>{0,-1,1,0}; //左旋转90度
        rotate[1]=vector<int>{0,1,-1,0}; //右旋转90度

        vector<int> pos(2,0);
        vector<int> pos_tmp(2,0);
        for(int i=0;i<commands.size();i++){
            if(commands[i]>0){
                int j=1;  
                while(j<=commands[i]){
                    pos_tmp=pos;
                    pos[0]=pos[0]+1*direction[0];
                    pos[1]=pos[1]+1*direction[1];
                    if(ob_set.find(make_pair(pos[0],pos[1]))!=ob_set.end()){
                        pos=pos_tmp;
                        //cout<<"back -- i:"<<i<<" "<<"commands[i]:"<<commands[i]<<" "<<"j:"<<j<<" "<<"pos: x:"<<pos[0]<<" "<<"y:"<<pos[1]<<endl;
                        break;
                    }
                    max_dis=(max_dis>pos[0]*pos[0]+pos[1]*pos[1]?max_dis:pos[0]*pos[0]+pos[1]*pos[1]);
                    //cout<<"i:"<<i<<" "<<"commands[i]:"<<commands[i]<<" "<<"j:"<<j<<" "<<"pos: x:"<<pos[0]<<" "<<"y:"<<pos[1]<<endl;
                    j++;
                }

            }else{
                int new_dir_x=0;
                int new_dir_y=0;
                if(commands[i]==-2){
                    new_dir_x=rotate[0][0]*direction[0]+rotate[0][1]*direction[1];
                    new_dir_y=rotate[0][2]*direction[0]+rotate[0][3]*direction[1];
                }else{
                    new_dir_x=rotate[1][0]*direction[0]+rotate[1][1]*direction[1];
                    new_dir_y=rotate[1][2]*direction[0]+rotate[1][3]*direction[1];
                }
                direction[0]=new_dir_x;
                direction[1]=new_dir_y;
            }
        }

        return max_dis;

    }
};